package com.rui.study.algorithm.P_股票_买卖股票最佳时机Ⅲ_最多两笔交易;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-07 09:09
 **/
public class Solution1移动分割点分别寻找最佳出售点 {



    public int maxProfit(int[] prices) {
        int n = prices.length;
        int maxProfit = maxProfit(0, n-1, prices);
        int tempProfit;
        for (int i = 1; i < n - 2; i++) {
            tempProfit = maxProfit(0, i, prices) + maxProfit(i + 1, n - 1, prices);
            if (tempProfit > maxProfit) maxProfit = tempProfit;
        }
        return maxProfit;
    }

    public int maxProfit(int begin, int end, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int maxProfit = 0;
        int min = prices[begin];
        for (int i = begin + 1; i <= end; i++) {
            min = Math.min(min, prices[i]);
            if (prices[i] - min > maxProfit) maxProfit = prices[i] - min;
        }
        return maxProfit;
    }

    public static void main(String[] args) {
//        int[] prices = {3,2,6,5,0,3};
//        int[] prices = {3,2,6,5,0,3,2,6};
        int[] prices = {1,4,2,7};
//        int[] prices = {1,2,4,2,5,7,2,4,9,0};
//        int[] prices = {48,12,60,93,97,42,25,64,17,56,85,93,9,48,52,42,58,85,81,84,69,36,1,54,23,15,72,15,11,94};
//        int[] prices = {48,12,60,93,97,42,25,64,17,56,85,93,9,48,52,42,58,85};
        Solution1移动分割点分别寻找最佳出售点 solution = new Solution1移动分割点分别寻找最佳出售点();
        long start = System.currentTimeMillis();
        int maxProfit = solution.maxProfit(prices);
        long end = System.currentTimeMillis();
        System.out.println("最大收益：" + maxProfit + ", 耗时：[" + (end - start) + "ms]");
    }

}
